Coursera week9
Anomaly Detection（異常検知）
100人健康診断をしたら数人は病気かもしれません。100個の商品を作れば数個は不良品があるかもしれません。そうした異常値を検出するためのアルゴリズムが、異常検知 (Anomaly Detection)です。
https://gyazo.com/c695a25a9c1b35d520f5c509eb0ba25e
上のデータで言えば、赤のデータポイントが明らかに外れ値 (Outlier)です。
数学的には、ガウシアン (正規分布)をデータにフィットして、あるデータ$ x^{(i)} の正規分布上の値$ p(x^{(i)}) が、閾値$ \epsilon より小さければ、外れ値とみなすことにします。
アルゴリズムは以下のようになります。異常値が入っているかもしれないデータ$ x に対して、そのときの説明変数を$ j=1, ..., n とすると、
①平均値$ \mu を求める。
$ \mu_j = \frac{1}{m}\sum_{i=1}^{m}x_j^{(i)}
②標準偏差$ \sigma^2 を求める。
$ \sigma^2_j = \frac{1}{m}\sum_{i=1}^{m}(x_j^{(i)} - \mu_j)^2
③異常値の可能性がある新しいデータ$ x_{test} を用いて、$ p(x_{test})を計算する。
$ p(x_{test}) = \prod_{j=1}^{n}p(x_j;\mu_j,\sigma_j^2) = \prod_{j=1}^{n}\frac{1}{\sqrt{2\pi}\sigma_j}exp(-\frac{(x_j - \mu_j)^2}{2\sigma^2_j})
④$ p(x_{test}) < \mu なら、$ x_{test} は異常値と判断。
データの分布がもともと正規分布ではない場合もあります。そんなときは、$ \sqrt{x} をとったり、$ \log(x)をとると正規分布化することができます。
https://gyazo.com/0d6f3aa5fb341b459284418f4e1e3109
閾値$ \mu の決め方ですが、基本的には概ね主観で決めます。ですが、数学的に、交差検定 (Cross Validation)を使ってより詳細に決める方法があります。
$ p(x) < \mu なら、$ anomaly (y = 1)
$ p(x) \geq \mu なら、$ normal (y = 0)
このように分類 (Classification)させ、モデル精度を確認します。モデル精度が上がるように$ \mu を決めます。
異常検知課題では、多くの場合データに偏りがあります (Skewed Data)。異常は全体の一部しかありません。そのため、モデル精度の確認には正答率 (Classification Accuracy)ではなく、F値 (Fscore)を用います。
Recommender System（レコメンダシステム）
オンラインショッピング、レストランのレビューサイトなど、ユーザーの行動データから好みを推定し、そのユーザーに合わせた商品なりサービスを提案するアルゴリズムが、インターネット上では溢れています。こうしたものをレコメンダシステム (Recommender System)といいます。
例えば、2016年の映画について、0 - 5段階で5人にレビューしてもらったとします。すると、以下のようになりました。
https://gyazo.com/7218b40eadc0dcb429b7e93257ea3b88
上のデータで言うと井上くんは、「君の名は」「聲の形」という2つのアニメを観て高評価をしていますが、「この世界の片隅に」を観ていません。もし観ていれば、きっと高評価をしているはずです。
一般的に、ユーザー$ j について、まだ観ていないある映画$ x^{(i)} のレビュー $ y^{(i, j)} は、モデルが学習したパラメーター$ \theta^{(j)} を用いて以下のように計算できます。
$ y^{(i, j)} = (\theta^{(j)})^Tx^{(i)}
モデルの学習は、各ユーザー毎に行います。もちろん、そのユーザーが観た映画からしか学習はできないので、各ユーザー、各映画において観ていたら1、観ていなければ0とする行列$ r(i, j) があると便利です。
また、映画の要素$ x^{(i)} とレビュー$ y^{(i, j)} からモデルパラメーター$ \theta^{(j)} を学習するだけでなく、$ \theta^{(j)} と$ y^{(i, j)} から$ x^{(i)} を学習することも必要になります。
これを可能にするのが、協調フィルタリング (Collaborative Filtering)です。このモデルは、θ→x→θ→x→...と交互にパラメーターを学習していきます。アルゴリズムは、以下のようになります。
Collaborative Filtering（協調フィルタリング）
①パラメーター$ x^{(1)}, ..., x^{(n_m)}, \theta^{(1)}, ..., \theta^{(n_u)}を小さなランダム値に初期化する (Symmetry Breaking)。
②目的関数 (Cost Function) $ J(x^{(1)}, ..., x^{(n_m)}, \theta^{(1)}, ..., \theta^{(n_u)}) の最小値を満たすパラメーター$ x, \theta を、最急降下法 (Gradient Descent)などを用いて計算する。
目的関数 (Cost Function)
$ J = \frac{1}{2}\sum_{(i, j):r(i, j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i, j)})^2 + \frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^{n}(x_k^{(i)})^2 + \frac{\lambda}{2}\sum_{i=1}^{n_u}\sum_{k=1}^{n}(\theta_k^{(j)})^2
Gradient Descent (最急降下法)
$ x_k^{(i)} := x_k^{(i)} - \alpha(\sum_{j:r(i, j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i, j)})\theta_k^{(j)} + \lambda x_k^{(i)})
$ \theta_k^{(i)} := \theta_k^{(j)} - \alpha(\sum_{j:r(i, j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i, j)})x_k^{(i)} + \lambda \theta_k^{(j)})
③学習して得られたパラメーター$ \theta, x を用いて、レビュー$ y を予測する。
$ y = (\theta^{(j)})^Tx^{(i)}
これで$ r(i,j)=0 で推定された$ y の値が高い映画$ i を、ユーザー$ j にオススメ(Recommend)することができます。